package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-11-04 20:29
 */

/**
 * 题目：
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 * <p>
 * 示例：
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class Test74_寻找两个正序数组的中位数 {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums2;
            nums2 = nums1;
            nums1 = temp;
        }

        int len1 = nums1.length;
        int len2 = nums2.length;
        int tal = (len1 + len2 + 1) / 2;
        int left = 0;
        int right = len1;

        //计算数组右边的数量
        while (left < right) {
            int i = left + (right - left + 1) / 2;
            int j = tal - i;
            if (nums1[i - 1] > nums2[j]) {
                right = i - 1;
            } else {
                left = i;
            }
        }
        int i = left;
        int j = tal - i;
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        int nums1rightMin = i == len1 ? Integer.MAX_VALUE : nums1[i];
        int nums2rightMin = j == len2 ? Integer.MAX_VALUE : nums2[j];

        if ((len1 + len2) % 2 == 1) {
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            return (double) (Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1rightMin, nums2rightMin)) / 2;
        }
    }
}
